class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
function detectCycle(head: ListNode | null): ListNode | null {

    let current: ListNode | null = head;
    const set = new Set();

    while (current) {     
        if(set.has(current)){
            return current;
        }
        set.add(current);
        current = current.next;
    }

    // 如果快指针到达链表末尾，说明无环
    return null;
};

// 使用快慢指针找到环内的相遇点

// 然后将一个指针移回头部，两个指针以相同速度前进

// 当它们再次相遇时，就是环的入口节点
function detectCycle1(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return null;

    let slow: ListNode | null = head;
    let fast: ListNode | null = head;

    // 第一阶段：判断是否有环，并找到相遇点
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;

        if (slow === fast) {//有环
            // 第二阶段：找到环的入口
            let ptr1: ListNode | null = head;
            let ptr2: ListNode | null = slow;

            while (ptr1 !== ptr2) {
                ptr1 = ptr1!.next;
                ptr2 = ptr2!.next;
            }

            return ptr1;
        }
    }

    return null;
}